package leetcode.code0235;

import leetcode.IDebug;
import leetcode.helper.tree.TreeNode;

public class Solution implements IDebug {

	TreeNode ans;

	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		ans = null;
		this.ancestor(root, p, q);
		return ans;
	}

	private int ancestor(TreeNode root, TreeNode p, TreeNode q) {
		if (root == null) {
			return 0;
		}
		int ans = 0;
		if (root == p) {
			ans |= 1;
		} else if (root == q) {
			ans |= 2;
		}
		ans = ans | this.ancestor(root.left, p, q);
		if (ans == 3) {
			this.ans = root;
			return 0;
		}
		ans = ans | this.ancestor(root.right, p, q);
		if (ans == 3) {
			this.ans = root;
			return 0;
		}
		return ans;
	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
